package com.cqs.leetcode.sort;


import java.util.Arrays;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

/**
 * @author lixiaowen
 * @create 2019-12-11
 */
public class SortTemplate {


    static class QuickSort {

        public void quickSort(int[] arr) {
            if (arr == null || arr.length <= 1) return;
            quickSort(arr, 0, arr.length - 1);
        }

        private void quickSort(int[] arr, final int left, final int right) {
            //递归终止条件
            if (left >= right) return;
            //左边第一个元素作为pivot
            int pivot = left;
            //定义两个工作指针
            int l = left + 1, r = right;
            while (l <= r) {
                while (l <= r && arr[l] <= arr[pivot]) {
                    ++l;
                }
                while (l <= r && arr[pivot] < arr[r]) {
                    --r;
                }
                if (l < r) {
                    swap(arr, l, r);
                }
            }
            swap(arr, pivot, r);
            //递归处理
            quickSort(arr, left, r - 1);
            quickSort(arr, r + 1, right);
        }
    }

    static class MergeSort {


        public void mergeSort(int[] arr) {
            if (arr == null || arr.length <= 1) return;
            //其求中点
            mergeSort(arr, 0, arr.length - 1);
        }

        private void mergeSort(int[] arr, int left, int right) {
            //1. 终止条件
            if (left >= right) return;
            int mid = (right + left) / 2;//可能会溢出
            //2. 数组拆分两部分
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);
            //3. 数组两部分已经分别有序,进行合并
            merge(arr, left, mid, right);
        }

        /**
         * 合并数组
         *
         * @param arr
         * @param left
         * @param mid
         * @param right
         */
        private void merge(int[] arr, int left, int mid, int right) {
            int[] tmp = new int[right - left + 1];
            //复制数组
            System.arraycopy(arr, left, tmp, 0, tmp.length);
            //注意细节： tmp数组只是arr数组的一部分。所以tmp右边的起始索引为mid + 1 - left
            int l = 0, r = mid + 1 - left;
            int cnt = left - 1;
            // (mid-left) 是tmp的中位数. (right - left )是tmp最右边的索引
            while (l <= (mid - left) && r <= (right - left)) {
                arr[++cnt] = tmp[l] <= tmp[r] ? tmp[l++] : tmp[r++];
            }
            //右测已经复制完毕
            if (l <= mid - left) {
                System.arraycopy(tmp, l, arr, (++cnt), (mid - l - left + 1));
            }
            //注意：左侧已经复制完毕情况,可以直接结束
        }

    }

    static class StackSort {

        public void sort(int[] arr) {
            //1.构建堆
            buildStack(arr);
            //2.最右元素与堆顶交换，数组逻辑长度减一
            int len = arr.length;
            while (--len > 0) {
                swap(arr,0,len);
                sink(arr,0,len - 1);
            }
        }

        private void buildStack(int[] arr) {
            //确定边界(从哪个结点开始构建堆)
            for (int i = arr.length / 2 - 1; i >= 0; --i) {
                //从低向顶构建  顶点下沉
                sink(arr,i,arr.length - 1);
            }
        }

        /**
         *
         * 下沉终止条件: 无孩子结点比父结点大
         *
         * @param arr
         * @param parent
         * @param right
         */
        private void sink(int[] arr, int parent, int right) {
            //保存最早的堆顶的值
            int origin = arr[parent];
            //需要有孩子结点比父节点要大
            while (true) {
                int child = 2 * parent + 1;
                //和最大的孩子结点交换
                if (child + 1 <= right && arr[child + 1] > arr[child]) {
                    ++child;
                }
                //注意 这里是origin
                if (child > right || (arr[child] <= origin)) break;
                //父节点更新。为了减少复制次数,孩子结点先不动
                arr[parent] = arr[child];
                //处理"堆顶"变化的子堆
                parent = child;
            }
            arr[parent] = origin;
        }

        /**
         * 插入的时候
         *
         * @param arr
         * @param child
         */
        private void swim(int[] arr, int child){
            int origin = arr[child];
            while (child > 1 && origin > arr[(child-1)/2]){
                arr[child] = arr[(child-1)/2];
                child = child / 2;
            }
            arr[child] = origin;
        }
    }

private static void swap(int[] arr, int left, int right) {
    int tmp = arr[left];
    arr[left] = arr[right];
    arr[right] = tmp;
}

    public static void main(String[] args) {
        int num = 100;
        int[] arrs = new int[num];
        for (int i = 0; i < num; i++) {
            arrs[i] = new Random().nextInt(1 * num);
        }
        List<Integer> list = Arrays.stream(arrs).boxed().collect(Collectors.toList());
        System.out.println(list);
        QuickSort quickSort = new QuickSort();

        //quickSort.quickSort(arrs);
        MergeSort mergeSort = new MergeSort();
//        mergeSort.mergeSort(arrs);
        StackSort stackSort = new StackSort();
        stackSort.sort(arrs);
        list = Arrays.stream(arrs).boxed().collect(Collectors.toList());
        System.out.println(list);



    }
}
